package heepstackqueue;

import java.util.Stack;

public class D230723 {
    // 用两个栈实现队列
    Stack<Integer> stack1 = new Stack<Integer>();
    Stack<Integer> stack2 = new Stack<Integer>();
    public void push(int node) {
        stack1.push(node);
    }
    public int pop() {
        if (stack2.isEmpty()) {
            while (!stack1.isEmpty()) {
                stack2.push(stack1.pop());
            }
        }
        return stack2.pop();
    }
}

// 包含min函数的栈
// 最小栈
class Solution {
    Stack<Integer> s1 = new Stack<>();  // 用来进行正常的 pop push 操作
    Stack<Integer> s2 = new Stack<>();  // 存放当前 s1 栈中，最小的元素，最小的在栈顶
    public void push(int node) {
        s1.push(node);
        if (s2.isEmpty() || s2.peek() >= node) {
            // 如果小于等于最小栈的栈顶，入栈
            s2.push(node);
        }
    }
    public void pop() {
        int tmp = s1.pop();
        if (tmp == s2.peek()) {
            // 出栈元素是当前最小元素，最小值出栈
            s2.pop();
        }
    }
    public int top() {
        return s1.peek();
    }
    public int min() {
        return s2.peek();
    }
}


// 有效括号序列
class Solution1 {
    public boolean isValid (String s) {
        char[] arr = s.toCharArray();
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == '{') {
                stack.push('}');
            } else if (arr[i] == '[') {
                stack.push(']');
            } else if (arr[i] == '(') {
                stack.push(')');
            } else if (stack.isEmpty() || stack.pop() != arr[i]) {
                return false;
            }
        }
        return stack.isEmpty();
    }
}
